    package sword.offer;

    /**
     * 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n级的台阶总共有多少种跳法。
     * 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
     * <p>
     * 链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
     *
     * @author 胡宇轩
     * @Email: yuxuan.hu01@bianlifeng.com
     */
    public class Ten2 {
        /**
         * 简单的动态规划问题
         * 青蛙跳到当前台阶，有两种跳法 即 从当前台阶的前一级 和 前二级
         * 我们也可以反过来想： 当青蛙第一次选择跳一级台阶 那么他还有剩余n-1级台阶  第一次选择跳两级台阶 那么他还有剩余n-2级台阶
         * 设f(n)为青蛙跳到n级台阶的跳法数量
         * 则 f(n) = f(n-2) + f(n-1)
         *
         */
        class Solution {
            public int numWays(int n) {
                if(n==0){
                    return 1;
                }
                if(n <= 2){
                    return n;
                }
                int a1=1, a2=2;
                int curr = 0;
                for (int i=3; i<=n; i++){
                    curr = (a1 + a2) % 1000000007;
                    a1 = a2;
                    a2=curr;
                }
                return curr;
            }
        }
    }
